import java.util.*;

public class Test {
    // 题目1：二叉树的最近公共祖先
    // 迭代的方式
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null){
            return right;
        }

        if(right == null){
            return left;
        }

        // left != null && right != null
        return root;
    }

    // 题目2：二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while(true){
            if(p.val < ancestor.val && q.val < ancestor.val){
                ancestor = ancestor.left;
            }else if(p.val > ancestor.val && q.val > ancestor.val){
                ancestor = ancestor.right;
            }else{
                break;
            }
        }
        return ancestor;
    }

    // 题目3：最小基因变化
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)){
            return 0;
        }
        Set<String> set = new HashSet<>();
        for(String s : bank){
            set.add(s);
        }
        if(!set.contains(endGene)){
            return -1;
        }

        Set<String> set1 = new HashSet<>();
        set1.add(startGene);
        int count = 0;
        char[] gene = {'A', 'T', 'G', 'C'};
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        while(!q.isEmpty()){
            count++;
            int sz = q.size();
            for(int k = 0; k < sz; k++){
                String str = q.poll();
                for(int i = 0; i < 8; i++){
                    char[] ch = str.toCharArray();
                    for(int j = 0; j < 4; j++){
                        ch[i] = gene[j];
                        String ss = new String(ch);
                        if(ss.equals(endGene)){
                            return count;
                        }
                        if(set.contains(ss) && !set1.contains(ss)){
                            q.offer(ss);
                            set1.add(ss);
                        }
                    }
                }
            }

        }
        return -1;
    }

    // 题目4：单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) return 0;
        Set<String> list = new HashSet<>();
        for(String s : wordList){
            list.add(s);
        }
        if(!list.contains(endWord)) return 0;
        Set<String> vis = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        vis.add(beginWord);
        q.offer(beginWord);
        int step = 1;
        int n = beginWord.length();
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            for(int k = 0; k < sz; k++){
                String str = q.poll();
                for(int i = 0; i < n; i++){
                    char[] chs = str.toCharArray();
                    for(char ch = 'a' ; ch <= 'z'; ch++){
                        chs[i] = ch;
                        String ss = new String(chs);
                        if(ss.equals(endWord)){
                            return step;
                        }

                        if(!vis.contains(ss) && list.contains(ss)){
                            q.offer(ss);
                            vis.add(ss);
                        }
                    }
                }
            }
        }
        return 0;
    }

    // 题目5：不浪费原料的汉堡制作方案
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        List<Integer> res = new LinkedList<>();
        if(tomatoSlices % 2 == 1){
            return res;
        }
        int y = tomatoSlices / 2 - cheeseSlices;
        int x = cheeseSlices - y;
        if(x >= 0 && y >= 0){
            res.add(y);
            res.add(x);
        }
        return res;
    }

    // 题目6：合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode node = dummyNode;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                node.next = list1;
                node = list1;
                list1 = list1.next;
            }else{
                node.next = list2;
                node = list2;
                list2 = list2.next;
            }
        }
        if(list1 == null){
            node.next = list2;
        }
        if(list2 == null){
            node.next = list1;
        }
        return dummyNode.next;
    }

    // 题目7：回文链表
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        ListNode curNext = null;
        while(cur != null){
            curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        while(head != slow ){
            if(head.val != slow.val){
                return false;
            }
            if(head.next == slow) return true;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    // 题目8：删除链表的节点
    public ListNode deleteNode(ListNode head, int val) {
        // 头删
        if(head.val == val){
            ListNode cur = head.next;
            head.next = null;
            return cur;
        }

        ListNode node =  frontNode(head, val);
        ListNode nodeNext = node.next;
        node.next = nodeNext.next;
        nodeNext.next = null;
        return head;
    }

    public ListNode frontNode(ListNode head, int val){
        ListNode node = new ListNode(-1);
        node.next = head;
        while(node.next != null){
            if(node.next.val == val){
                return node;
            }
            node = node.next;
        }
        return null;
    }



}
